mind_controlfandomcom-20200223-history
MD4
MD4 (Message Digest 4) — хеш-функция, разработанная профессором Массачусетского университета Рональдом Ривестом в 1990 году, и впервые описанная в RFC 1186. Для произвольного входного сообщения функция генерирует 128-разрядное хеш-значение, называемое дайджестом сообщения. Этот алгоритм используется в протоколе аутентификации MS-CHAP, разработанном корпорацией Майкрософт для выполнения процедур проверки подлинности удаленных рабочих станций Windows. Является предшественником MD5. Алгоритм MD4 Предполагается, что на вход подано сообщение, состоящее из ~b~ бит, хеш которого нам предстоит вычислить. Здесь ~b~ — произвольное неотрицательное целое число; оно может быть нулем, не обязано быть кратным восьми, и может быть сколь угодно большим. Запишем сообщение побитово, в виде: m_0 m_1 \ldots m_{b-1} Ниже приведены 5 шагов, используемые для вычисления хеша сообщения. Шаг 1. Добавление недостающих битов. Сообщение расширяется так, чтобы его длина в битах по модулю 512 равнялась 448. Таким образом, в результате расширения, сообщению недостает 64 бита до длины, кратной 512 битам. Расширение производится всегда, даже если сообщение изначально имеет нужную длину. Расширение производится следующим образом: один бит, равный 1, добавляется к сообщению, а затем добавляются биты, равные 0, до тех пор, пока длина сообщения не станет равной 448 по модулю 512. В итоге, к сообщению добавляется как минимум 1 бит, и как максимум 512. Шаг 2. Добавление длины сообщения. 64-битное представление ~b~ (длины сообщения перед добавлением набивочных битов) добавляется к результату предыдущего шага. В маловероятном случае, когда ~b~ больше, чем 2^{64} , используются только 64 младших бита. Эти биты добавляются в виде двух 32-битных слов, и первым добавляется слово, содержащее младшие разряды. На этом этапе (после добавления битов и длины сообщения) мы получаем сообщение длиной кратной 512 битам. Это эквивалентно тому, что это сообщение имеет длину, кратную 16-ти 32-битным словам. Пусть M\ldots N-1 означает массив слов получившегося сообщения (здесь N кратно 16). Шаг 3. Инициализация MD-буфера. Для вычисления хеша сообщения используется буфер, состоящий из 4 слов (32-битных регистров): ~(A,B,C,D) . Эти регистры инициализируются следующими шестнадцатеричными числами (младшие байты сначала): word A : 01 23 45 67 word B : 89 ab cd ef word C : fe dc ba 98 word D : 76 54 32 10 Шаг 4. Обработка сообщения блоками по 16 слов. Для начала определим три вспомогательные функции, каждая из которых получает на вход три 32-битных слова, и по ним вычисляет одно 32-битное слово. F(X,Y,Z) = XY \lor \neg X Z G(X,Y,Z) = XY \lor XZ \lor YZ H(X,Y,Z) = X \oplus Y \oplus Z На каждую битовую позицию F действует как условное выражение: если X , то Y ; иначе Z . Функция F могла бы быть определена с использованием ~+ вместо \lor , поскольку ~XY и \neg XZ не могут равняться 1 одновременно. G действует на каждую битовую позицию как функция максимального значения: если по крайней мере в двух словах из X, Y, Z соответствующие биты равны 1 , то G выдаст 1 в этом бите, а иначе G выдаст бит, равный 0 . Интересно отметить, что если биты X , Y и Z статистически независимы, то биты F(X,Y,Z) и G(X,Y,Z) будут также статистически независимы. Функция H реализует побитовый xor , она обладает таким же свойством, как F и G . Алгоритм хеширования на абстрактном языке программирования: /* Обрабатываем каждый блок из 16-ти слов */ for i = 0 to N/16-1 do /* Заносим i-ый блок в переменную X */ for j = 0 to 15 do set Xj to Mi*16+j. end /* конец цикла по j */ /* Сохраняем A как AA, B как BB, C как CC, и D как DD */ AA = A BB = B CC = C DD = D /* Раунд 1 */ /* Пусть k s означает следующую операцию: a = (a + F(b,c,d) + Xk) <<< s. */ /* Производим 16 следующих операций: */ 0 3 1 7 2 11 3 19 4 3 5 7 6 11 7 19 8 3 9 7 10 11 11 19 12 3 13 7 14 11 15 19 /* Раунд 2 */ /* Пусть k s означает следующую операцию: a = (a + G(b,c,d) + Xk + 5A827999) <<< s. */ /* Производим 16 следующих операций: */ 0 3 4 5 8 9 12 13 1 3 5 5 9 9 13 13 2 3 6 5 10 9 14 13 3 3 7 5 11 9 15 13 /* Раунд 3 */ /* Пусть k s означает следующую операцию: a = (a + H(b,c,d) + Xk + 6ED9EBA1) <<< s. */ /* Производим 16 следующих операций: */ 0 3 8 9 4 11 12 15 2 3 10 9 6 11 14 15 1 3 9 9 5 11 13 15 3 3 11 9 7 11 15 15 /* Затем производим следующие операции сложения. (Увеличиваем значение в каждом регистре на величину, которую он имел перед началом итерации по i */ A = A + AA B = B + BB C = C + CC D = D + DD end /* конец цикла по i */ Замечание. Величина 5A827999 — шестнадцатеричная 32-битная константа, первые байты — старшие. Она представляет собой квадратный корень из 2. Она же в восьмеричном представлении: 013240474631. Величина 6ED9EBA1 — шестнадцатеричная 32-битная константа, первые байты — старшие. Она представляет собой квадратный корень из 3. Она же в восьмеричном представлении: 015666365641. Эти данные приведены в книге Кнут, Искусство программирования, издание 1981 года, том 2, стр 660, таблица 2. Шаг 5. Формирование хеша. Результат (хеш-функция) получается как ABCD. То есть, мы выписываем 128 бит, начиная с младшего бита A, и заканчивая старшим битом D. Реализация алгоритма на языке C содержится в RFC 1320. Примеры хешей 128-битные MD4 хеши представляют собой 32-х значное число в 16-ричном формате. В следующем примере показан хеш 43-байтной строки ASCII: MD4("The quick brown fox jumps over the lazy dog") = 1bee69a46ba811185c194762abaeae90 Любое даже самое незначительное изменение хешируемой информации приводит к получению полностью отличного хеша, например, изменение в примере одной буквы с d на c: MD4("The quick brown fox jumps over the lazy 'c'og") = b86e130ce7028da59e672d56ad0113df Пример MD4 хеша для «нулевой» строки: MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0 Сравнение с MD5 * MD4 использует три цикла из 16 шагов каждый, в то время как MD5 использует четыре цикла из 16 шагов каждый. * В MD4 дополнительная константа в первом цикле не применяется. Аналогичная дополнительная константа используется для каждого из шагов во втором цикле. Другая дополнительная константа используется для каждого из шагов в третьем цикле. В MD5 различные дополнительные константы, Тi, применяются для каждого из 64 шагов. * MD5 использует четыре элементарные логические функции, по одной на каждом цикле, по сравнению с тремя в MD4, по одной на каждом цикле. * В MD5 на каждом шаге текущий результат складывается с результатом предыдущего шага. Например, результатом первого шага является измененное слово А. Результат второго шага хранится в D и образуется добавлением А к циклически сдвинутому влево на определенное число бит результату элементарной функции. Аналогично, результат третьего шага хранится в С и образуется добавлением D к циклически сдвинутому влево результату элементарной функции. MD4 это последнее сложение не включает. Безопасность Уровень безопасности, закладывавшийся в MD4, был рассчитан на создание достаточно устойчивых гибридных систем электронной цифровой подписи, основанных на MD4 и криптосистеме с открытым ключом. Рональд Ривест MD4 считал, что алгоритм хеширования можно использовать и для систем, нуждающихся в сильной криптостойкости. Но в то же время он отмечал, что MD4 создавался прежде всего как очень быстрый алгоритм хеширования, поэтому он может быть плох в плане криптостойкости. Как показали последовавшие исследования, он был прав, и для приложений, где важна прежде всего криптостойкость, стал использоваться алгоритм MD5. Уязвимости Уязвимости в MD4 были продемонстрированы в статье Берта ден Боера и Антона Босселариса в 1991 году. Первая коллизия была найдена Гансом Доббертином в 1996 году. См. также * MD2 * MD5 * HAVAL * SHA-1 Ссылки * RFC 1186 * RFC 1320 * Paj’s Home: Cryptography — Реализация MD4 на JavaScript. Так же поддерживает MD5 и SHA-1. Опубликовано под BSD License. Также содержит ссылки на несколько других реализаций. * Реализация MD4 на PHP — Основана на JavaScript реализации Пола Джонсона. Поиск коллизий * Improved Collision Attack on MD4 Категория:Криптографические хеш-функции da:MD4 de:Message-Digest Algorithm 4 en:MD4 es:MD4 fr:MD4 he:MD4 hr:MD4 it:MD4 ja:MD4 nl:MD4 pl:MD4 pt:MD4 sr:MD4 tg:MD4 zh:MD4